#include <stdio.h>
#include <stdlib.h>


typedef int ElemType;
typedef struct DuLNode {
    ElemType data;
    struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;

void InitList_DuL(DuLinkList &L) {
    L = (DuLNode *) malloc(sizeof(DuLNode));  // 申请存放一个结点数据所需要的内在空间
    if (!L) exit(1);                        // 存储分配失败
    L->next = NULL;                            // 表头结点的后继指针域置空
    L->prior = NULL;                           // 表头结点的前驱指针域置空
}

int ListLength_Dul(DuLinkList L) {
    DuLinkList p;
    int k = 0;
    p = L->next;
    while (p)             //当p所指向的结点还有值
    {
        k++;
        p = p->next;
    }
    return k;
}// ListLength_Dul



bool ListInsert_DuL(DuLinkList &L, int i, ElemType e) {
    // 在带头结点的双向链表L中第i个结点之前插入元素e
    DuLinkList p, s, q;
    int j;
    q = L;
    j = 0;
    while (q->next && j < i - 1) {
        q = q->next;
        j++;
    }   // 寻找第i-1个结点,并让q指向此结点
    if (j != i - 1) return false;                   // i的位置不合理
    s = (DuLNode *) malloc(sizeof(DuLNode));
    if (!s) exit(1);                            // 存储分配失败
    s->data = e;
    if (q->next)                                   // 插入的位置不是表尾
    {
        p = q->next;                                  // p指向待插入的位置
        s->prior = p->prior;                          // 修改指针
        p->prior->next = s;
        s->next = p;
        p->prior = s;
    } else                                     // 插入的位置是表尾
    {
        q->next = s;
        s->prior = q;
        s->next = NULL;
    }
    return true;
}

bool ListDelete_DuL(DuLinkList &L, int i, ElemType &e) {
    // 删除带有头结点的双向链表L中的第i个结点，并让e返回其值
    DuLinkList p;
    int j;
    p = L;
    j = 0;
    while (p->next && j < i) {
        p = p->next;
        j++;
    }      // 寻找第i个结点,并让p指向此结点
    if (j != i) return false;                 // i的位置不合理
    if (p->next)                              // 待删除的不是表尾结点
        p->next->prior = p->prior;               // 结点p的前驱作为结点p的后继的前驱
    p->prior->next = p->next;                // 结点p的后继作为结点p的前驱的后继
    e = p->data;
    free(p);
    return true;
}

void ListTraverse_DuL(DuLinkList L) {
    DuLNode *p = L->next;
    while (p != L) {
        printf("%d\t", p->data);
        p = p->next;
    }
}


/*
 * 17.设计一个算法用于判断带头结点的循环双链表是否对称
 * 操作步骤：用p和q依次遍历A和B中的元素，若p.data=q.data,则p、q后移；若p.data!=q.data,则p后移, q从B从头开始。
 */
//判断循环双链表是否对称
int Symmetry(DuLinkList L) {
    DuLNode *p = L->next, *q = L->prior;
    while (p != q && p->next != p)
        if (p->data == q->data) {
            p = p->next;
            q = q->prior;
        } else
            return 0;
    return 1;
}

int main() {
    DuLinkList L;
    InitList_DuL(L);
    printf("***********创建链表***********\n");
    int a[] = {2, 4, 8, 16, 32, 8, 128, 256, 1, 3, 9};

    for (int i = 0; i < 10; i++) {
//        printf("插入元素%d\n", a[i]);
        ListInsert_DuL(L, i, a[i]);
    }
    printf("使用头插法创建了一个带头结点的单链表，表长为：%d\n", ListLength_Dul(L));
    printf("表中的元素依次是：");
    ListTraverse_DuL(L);
    return 0;
}
